﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <cstring>
#include <memory>
#include <functional>
#include <algorithm>
#include <assert.h>

using namespace std;

//void AdjustDown(vector<int>& a, int parent, int n) {
//	int child = parent * 2 + 1;
//	while (child < n) {
//		if (child + 1 < n && a[child] < a[child + 1]) {
//			child++;
//		}
//		if (a[parent] < a[child]) swap(a[parent], a[child]);
//		else break;
//		parent = child;
//		child = parent * 2 + 1;
//	}
//}
//void AdjustUp(vector<int>& a, int child) {
//	int parent = (child - 1) / 2;
//	while (child > 0) {
//		if (a[parent] > a[child]) swap(a[parent], a[child]);
//		else break;
//		child = parent;
//		parent = (child - 1) / 2;
//	}
//}
//
//void AdjustDownHeap(vector<int>& a) {
//	int n = a.size();
//	for (int parent = (n - 1) / 2; parent >= 0; parent--) {
//		AdjustDown(a, parent, n);
//	}
//
//	for (auto e : a) cout << e << ' ';
//	cout << endl;
//}
//void AdjustUpHeap(vector<int>& a) {
//	for (int child = 1; child < a.size(); child++) {
//		AdjustUp(a, child);
//	}
//
//	for (auto e : a) cout << e << ' ';
//	cout << endl;
//}
////
////void HeapSort(vector<int>& a) {
////	int n = a.size();
////	for (int parent = (n - 1) / 2; parent >= 0; parent--) {
////		AdjustDown(a, parent, n);
////	}
////	
////	int end = n - 1;
////	while (end > 0) {
////		swap(a[end], a[0]);
////		AdjustDown(a, 0, end);
////		end--;
////	}
////
////	for (auto e : a) cout << e << ' ';
////	cout << endl;
////}
////int main()
////{
////	vector<int> a{ 4,8,3,0,7,1,6 };
////	AdjustDownHeap(a);
////	AdjustUpHeap(a);
////	HeapSort(a);
////	return 0;
////}
//
//
//void InsertSort(vector<int>& v) {
//	int n = v.size();
//	for (int i = 1; i < n; i++) {
//		int data = v[i];
//		int j = i - 1;
//		while (j >= 0) {
//			if (v[j] <= data) break;
//			v[j + 1] = v[j];
//			j--;
//		}
//		v[j + 1] = data;
//	}
//}
//void ShellSort(vector<int>& v, int n) {
//	int distance = n;
//	while (true) {
//		for (int i = 0; i < distance; i++) {
//			for (int j = i + distance; j < n; j += distance) {
//				int data = v[j];
//				int k = j - distance;
//				while (k >= 0) {
//					if (v[k] >= data) break;
//					v[k + distance] = v[k];
//					k -= distance;
//				}
//				v[k + distance] = data;
//			}
//		}
//		if (distance == 1) break;
//		distance = distance / 3 + 1;
//	}
//}
//void SelectSort(vector<int>& v) {
//	int n = v.size();
//	int begin = 0, end = n - 1;
//	while (begin < end) {
//		int Min = begin, Max = end;
//		for (int i = begin; i <= end; i++) {
//			if (v[Min] > v[i]) Min = i;
//			if (v[Max] < v[i]) Max = i;
//		}
//		swap(v[Min], v[begin]);
//		if (Max == begin) {
//			Max = Min;
//		}
//		swap(v[end], v[Max]);
//		begin++;
//		end--;
//	}
//}
//void HeapSort(vector<int>& a) {
//	int n = a.size();
//	for (int parent = (n - 1) / 2; parent >= 0; parent--) {
//		AdjustDown(a, parent, n);
//	}
//	
//	int end = n - 1;
//	while (end > 0) {
//		swap(a[end], a[0]);
//		AdjustDown(a, 0, end);
//		end--;
//	}
//}
//void Sort(vector<int>& v) {
//	int n = v.size();
//	for (int i = 1; i < n; i++) {
//		for (int j = 0; j < n - i; j++) {
//			if (v[j] < v[j + 1]) {
//				swap(v[j], v[j + 1]);
//			}
//		}
//	}
//}
//
//int GetMid(vector<int>& v, int begin, int end) {
//	int n = v.size();
//	int mid = (0 + n - 1) / 2;
//	if (v[begin] < v[mid]) {
//		if (v[mid] < v[end]) return mid;
//		if (v[end] < v[begin]) return begin;
//	}
//	else {
//		if (v[mid] > v[end]) return mid;
//		if (v[end] > v[begin]) return begin;
//	}
//	return end;
//}
//int PartSort1(vector<int>& v, int begin, int end) {
//	int mid = GetMid(v, begin, end);
//	swap(v[begin], v[mid]);
//	int key = begin;
//	while (end > begin) {
//		while (end > begin && v[end] >= v[key]) {
//			end--;
//		}
//		while (end > begin && v[begin] <= v[key]) {
//			begin++;
//		}
//		swap(v[end], v[begin]);
//	}
//	swap(v[end], v[key]);
//	return end;
//}
//int PartSort2(vector<int>& v, int begin, int end) {
//	int mid = GetMid(v, begin, end);
//	swap(v[begin], v[mid]);
//	int key = v[begin];
//	while (end > begin) {
//		while (end > begin && v[end] <= key) {
//			end--;
//		}
//		v[begin] = v[end];
//		while (end > begin && v[begin] >= key) {
//			begin++;
//		}
//		v[end] = v[begin];
//	}
//	v[end] = key;
//	return end;
//}
//int PartSort3(vector<int>& v, int begin, int end) {
//	int mid = GetMid(v, begin, end);
//	swap(v[begin], v[mid]);
//	int key = begin;
//	int back = begin, front = begin + 1;
//	while (front <= end) {
//		if (v[front] < v[key]) {
//			swap(v[++back], v[front]);
//		}
//		front++;
//	}
//	swap(v[back], v[key]);
//	return back;
//}
//void QuickSort1(vector<int>& v, int begin, int end) {
//	if (begin >= end) return;
//	int key = PartSort3(v, begin, end);
//	QuickSort1(v, begin, key - 1);
//	QuickSort1(v, key + 1, end);
//}
//void QuickSort2(vector<int>& v) {
//	stack<int> s;
//	int begin = 0, end = v.size() - 1;
//	s.push(end);
//	s.push(begin);
//	while (!s.empty()) {
//		begin = s.top();
//		s.pop();
//		end = s.top();
//		s.pop();
//		int key = PartSort2(v, begin, end);
//		if (key - 1 > begin) {
//			s.push(key - 1);
//			s.push(begin);
//		}
//		if (key + 1 < end) {
//			s.push(end);
//			s.push(key + 1);
//		}
//	}
//}
//
//void MergeSort1(vector<int>& v, int begin, int end) {
//	if (begin >= end) return;
//	int middle = (begin + end) / 2;
//	MergeSort1(v, begin, middle);
//	MergeSort1(v, middle + 1, end);
//	
//	int leftbegin = begin, leftend = middle;
//	int rightbegin = middle + 1, rightend = end;
//	vector<int> cv;
//	while (leftbegin <= leftend && rightbegin <= rightend) {
//		if (v[leftbegin] >= v[rightbegin]) cv.push_back(v[leftbegin++]);
//		else cv.push_back(v[rightbegin++]);
//	}
//	while (leftbegin <= leftend) cv.push_back(v[leftbegin++]);
//	while (rightbegin <= rightend) cv.push_back(v[rightbegin++]);
//	
//	for (auto e : cv) v[begin++] = e;
//}
//void MergeSort2(vector<int>& v) {
//	int gap = 1;
//	int n = v.size();
//	vector<int> cv(n);
//	while (gap < n - 1) {
//		for (int i = 0; i < n; i += 2 * gap) {
//			int leftbegin = i, leftend = i + gap - 1;
//			int rightbegin = i + gap, rightend = rightbegin + gap - 1;
//			int insert = leftbegin;
//			if (rightbegin >= n) break;
//			if (rightend >= n) rightend = n - 1;
//
//			while (leftbegin <= leftend && rightbegin <= rightend) {
//				if (v[leftbegin] <= v[rightbegin]) cv[insert++] = v[leftbegin++];
//				else cv[insert++] = v[rightbegin++];
//			}
//			while (leftbegin <= leftend) cv[insert++] = v[leftbegin++];
//			while (rightbegin <= rightend) cv[insert++] = v[rightbegin++];
//		}
//		v.swap(cv);
//		gap *= 2;
//	}
//}
//
//void Print(vector<int>& v) {
//	for (auto e : v) cout << e << ' ';
//	cout << endl << endl;
//}

//int main()
//{
//
//	vector<int> v1{ 4,8,3,0,7,1,6 };
//	vector<int> v2{ 4,8,3,0,7,1,6 };
//	vector<int> v3{ 9,4,8,3,0,7,1,6 };
//	vector<int> v4{ 9,4,8,3,0,7,1,6 };
//	vector<int> v5{ 9,4,8,3,0,7,1,6 };
//	vector<int> v6{ 9,4,8,3,0,7,1,6 };
//	vector<int> v7{ 9,4,8,3,0,7,1,6 };
//	vector<int> v8{ 9,4,8,3,0,7,1,6 };
//	vector<int> v9{ 9,4,8,3,0,7,1,6 };
//
//	InsertSort(v1);
//	ShellSort(v2, v2.size());
//	SelectSort(v3);
//	HeapSort(v4);
//	Sort(v5);
//	QuickSort1(v6, 0, v6.size() - 1);
//	QuickSort2(v7);
//	MergeSort1(v8, 0, v8.size() - 1);
//	MergeSort2(v9);
//
//	Print(v1);
//	Print(v2);
//	Print(v3);
//	Print(v4);
//	Print(v5);
//	Print(v6);
//	Print(v7);
//	Print(v8);
//	Print(v9);
//	return 0;
//}

// 快排中插入直接插入算法，进行小区间优化
//void QuickSort3(int* a, int begin, int end)
//{
//	if (begin >= end)
//		return;
//
//	// 小区间优化，小区间不再递归分割排序，降低递归次数
//	if ((end - begin + 1) > 10)
//	{
//		int keyi = PartSort3(a, begin, end);
//
//		// [begin, keyi-1] keyi [keyi+1, end]
//		QuickSort1(a, begin, keyi - 1);
//		QuickSort1(a, keyi + 1, end);
//	}
//	else
//	{
//		InsertSort(a + begin, end - begin + 1);
//	}
//}

//class String
//{
//public:
//	typedef char* iterator;
//	typedef const char* const_iterator;
//public:
//	String(const char* str = "") : _size(0), _capacity(0), _str(nullptr)
//	{
//		_size = strlen(str);
//		_capacity = _size + 1;
//		_str = new char[_capacity];
//		memcpy(_str, str, _capacity);
//	}
//	String(const String& s)
//	{
//		_size = s._size;
//		_capacity = s._capacity;
//		_str = new char[s._capacity];
//		memcpy(_str, s._str, s._size + 1);
//	}
//	String& operator=(const String& s)
//	{
//		_size = s._size;
//		_capacity = s._capacity;
//		delete[] _str;
//		_str = new char[s._capacity];
//		memcpy(_str, s._str, s._size + 1);
//		return *this;
//	}
//
//	void reserve(size_t capacity)
//	{
//		if (capacity <= _capacity) return;
//		char* str = new char[capacity];
//		memcpy(str, _str, _size + 1);
//		delete[] _str;
//		_str = str;
//	}
//	void push_back(const char s)
//	{
//		if (_capacity == _size + 1)
//		{
//			reserve(2 * _capacity);
//		}
//		_str[_size++] = s;
//		_str[_size] = '\0';
//	}
//	void pop_back()
//	{
//		assert(_size > 0);
//		_str[--_size] = '\0';
//	}
//	size_t find(const char s)
//	{
//		for (int i = 0; i < _size; i++)
//		{
//			if (_str[i] == s) return i;
//		}
//		return string::npos;
//	}
//	size_t rfind(const char s)
//	{
//		for (int i = _size - 1; i >= 0; i--)
//		{
//			if (_str[i] == s) return i;
//		}
//		return string::npos;
//	}
//	iterator begin()
//	{
//		return _str;
//	}
//	iterator end()
//	{
//		return _str + _size;
//	}
//	const_iterator begin() const
//	{
//		return (const_iterator)_str;
//	}
//	const_iterator end() const
//	{
//		return (const_iterator)_str + _size;
//	}
//
//	iterator insert(const_iterator it, const char s)
//	{
//		int pos = it - begin();
//		assert(pos >= 0 && pos <= _size);
//		if (_capacity == _size + 1) reserve(2 * _capacity);
//		for (int i = _size; i >= pos; i--)
//		{
//			_str[i + 1] = _str[i];
//		}
//		_str[pos] = s;
//		_size++;
//		return _str + pos;
//	}
//	size_t size() { return _size; }
//	size_t capacity() { return _capacity; }
//	bool empty() { return _size == 0; }
//	
//	char& operator[](size_t pos)
//	{
//		assert(pos >= 0 && pos <= _size - 1);
//		return _str[pos];
//	}
//	void clear()
//	{
//		memcpy(_str, 0, _size);
//		_size = 0;
//	}
//	~String()
//	{
//		delete[] _str;
//		_str = nullptr;
//	}
//private:
//	char* _str;
//	size_t _size;
//	size_t _capacity;
//};

template <class T>
class Vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
public:

private:
	iterator _start;
	iterator _finish;
	size_t _capacity;
};



//class Solution {
//public:
//    int candy(vector<int>& ratings) {
//        int n = ratings.size();
//        int numbers = 0;
//        vector<int> v(n, 1);
//        for (int i = 1; i < n; i++) {
//            if (ratings[i] > ratings[i - 1]) {
//                v[i] = v[i - 1] + 1;
//            }
//        }
//        for (int i = n - 2; i >= 0; i--) {
//            if (ratings[i] > ratings[i + 1] && v[i] <= v[i + 1]) {
//                v[i] = v[i + 1] + 1;
//            }
//            numbers += v[i];
//        }
//        for (auto e : v) cout << e << ' ';
//        return numbers + v[n - 1];
//    }
//};


//class Solution {
//public:
//    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
//        int n = gas.size();
//        int index = -1;
//        int data = 0, mindata = INT_MAX;
//        for (int i = 0; i < n; i++) {
//            data += gas[i] - cost[i];
//            if (mindata > data) {
//                mindata = data;
//                index = i;
//            }
//        }
//        return data < 0 ? -1 : (index + 1) % n;
//    }
//};

//class Solution {
//public:
//    int hIndex(vector<int>& citations)
//    {
//        int h = 0;
//        sort(citations.begin(), citations.end(), greater<int>());
//        for (int i = 0; i < citations.size(); i++)
//        {
//            if (citations[i] >= i + 1) h++;
//            else break;
//        }
//        return h;
//    }
//};

//class Solution {
//public:
//    vector<int> productExceptSelf(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> vleft(n, 1);
//        vector<int> vright(n, 1);
//        vector<int> answer(n);
//        int x = 1;
//        for (int i = 1; i < n; i++) {
//            x *= nums[i - 1];
//            vleft[i] = x;
//        }
//        x = 1;
//        for (int i = n - 2; i >= 0; i--) {
//            x *= nums[i + 1];
//            vright[i] = x;
//        }
//        for (int i = 0; i < n; i++) {
//            answer[i] = vleft[i] * vright[i];
//        }
//        return answer;
//    }
//};


//class Solution {
//public:
//    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
//        int n = gas.size();
//        int x = -1;
//        vector<int> dp(2 * n, -1);
//        for (int i = 0; i < n; i++) {
//            dp[i] = gas[i];
//            for (int j = i + 1; j <= i + n; j++) {
//                dp[j] = dp[j - 1] - cost[(j - 1) % n];
//                if (dp[j] >= 0) dp[j] += gas[j % n];
//                else break;
//            }
//            if (dp[i + n] >= 0) x = i;
//        }
//        return x;
//    }
//};


